KURZUS: Alkalmazott operációkutatás

MODUL: I. modul: Az operációkutatás tárgya és módszerei

5. lecke: Szállítási feladat lineáris programozási modellje és megoldása

|  | Tanulási útmutató
| A szállítási feladat értelmezése, matematikai modellje és megoldása a tankönyv 4.1. és 4.2. fejezetében található.
| Nagyon fontos, hogy megismerje és rögzítse a szakirodalomban használatos fogalmakat, jelöléseket. A modell skaláris formája, a tömör vektormátrix szimbólumokkal adott formája a tankönyvben található. A lineáris programozás lényegének és modelljének megértése után ez is könnyen érthető lesz. Ha mégis gondot jelent, akkor tanulmányozza át a tankönyvben található példát. A lényeg az, hogy minden körülmények között fel tudja írni az ilyen szöveges feladat modelljét.
| Eddig azt az esetet tárgyaltuk, hogy a feladók készlete megegyezett a megrendelők igényével. Ez általában nem teljesül.
| Tegyük fel, hogy a tankönyv 4.2. fejezetében található példában a második feladónak 40 tonna a készlete és azt, hogy az első feladótól a 2. megrendelőnek technikai okok miatt nem lehet szállítani. Viszont szeretnénk, ha a 3. feladótól minden árut elszállítanánk (hiszen az a sógorom!).
| Ekkor biztos, hogy valamelyik feladónál marad áru, ezért nem egyenlőség formájában kell megfogalmazni a feltételi egyenleteket!
| Így tehát a modell:
| Feladókra: x 11 + x 12 + x 13 + x 14 ≤ 50 x 21 + x 22 + x 23 + x 24 ≤ 40 x 31 + x 32 + x 33 + x 34 = 20
| (Az utolsó sorban azért =, mert mindet el kell szállítani.)
| Rendelőkre x 11 + x 21 + x 31 = 40 x 12 + x 22 + x 32 = 30 x 13 + x 23 + x 33 = 20 x 14 + x 24 + x 34 = 10
| Itt minden igény teljesíthető, hiszen a készlet több mint az igény!
| Valamint x 12 =0, mert az első feladó nem szállíthat a 2. megrendelőnek.
| Célfüggvény:
| 8 x 11 +10 x 12 +9 x 13 +2 x 14 + x 21 +6 x 22 +4 x 23 +10 x 24 +3 x 31 +4 x 32 +5 x 33 + x 34 →min⁡.
| Ha az igény nagyobb, mint a készlet, akkor az igényt kifejező relációk (azaz a rendelőkre felírtak) lesznek ≤ értelműek!
| A szállítási feladat speciális lineáris programozási feladat, ezért az Excel-táblázaton az adatokat és a változókat is érdemes tömören, mátrix formában kijelölni. A következő Excel-képernyő mutatja ezt a célszerű elhelyezést.
| Az F oszlop celláiba az adott sor összege kerül, ezt az F2 cellába beírjuk, majd a többibe átmásoljuk (F3, F4, F6).
| A 6. sor celláiba az adott oszlop összege kerül, pl. a B6 cellába =SZUM(B2:B4).
| A célfüggvény képletét a G7 cellába írjuk be: =SZORZATÖSSZEG(B2:E4;$B$10:$E$12).
| Korlátozó feltételek (egyenként kell felvenni őket):
| $B$6:$E$6=$B$7: $E$7 $C$2=0 $F$26: $F$4<=$G$27: $G$4
| Ezután kell meghívni a Solver programot és értelemszerűen elhelyezni a modell elemeit.
| Ne feledkezzünk meg az x12=0 egyenlőségről és a beállításokról sem! Azaz a korlátozó feltételeknél a C2 cellát egyenlővé kell tenni nullával.
| A megoldás gombra kattintva kapjuk meg az eredményt.
| Tevékenységek
| Figyelmesen olvassa el a tankönyv 91. oldalát. Rögzítse a jelöléseket. Tanulmányozza a szállítási feladatot, gyakorolja a modell felírását! Gyakorolja a modell elhelyezését az Excel táblázatkezelőn, majd oldja meg Solver segítségével. Mindig ellenőrizze, hogy a számítógép segítségével kapott megoldás lehet-e az eredeti feladat optimális megoldása, ugyanis több helyen lehet hibát ejteni az adat bevitel és a modell felírása során!
| Követelmények
| Fel tudja írni a szövegesen adott szállítási feladat matematikai modelljét. A szállítási feladat adott modelljét célszerűen el tudja helyezni az Excel táblázatkezelőn. Solver segítségével meg tudja határozni adott szállítási feladat optimális megoldását.

|  | Önellenőrző feladatok
| 1. Tegyük fel, hogy három feladóhelyen (F1...F3) 100, 120 és 150 tonna áru van. Négy megrendelőhöz (R1...R4) kell szállítani rendre 80, 110, 90, 120 tonnát. A 3. feladótól az 1. megrendelőnek technikai okok miatt nem lehet szállítani, továbbá a 2. megrendelő igényét (hiszen a sógorom) teljesen ki kell elégíteni.
| A szállítási költségek mátrixa a következő (100 Ft/tonna):
| R1 | R2 | R3 | R4
F1 | 8 | 2 | 4 | 17
F2 | 7 | 14 | 3 | 2
F3 | 12 | 5 | 15 | 9
| a) Írja fel a feladat lineáris programozási modelljét! Vegyen elő egy lapot ott írja fel a feltételi egyenleteket és a célfüggvényt. Ezt használja a kérdések megválaszolására.
Ha kisebb-egyenlő, vagy nagyobb-egyenlő relációt kell írnia, akkor azt így adja meg: <=, illetve >=. | b) Írja fel a feladókra vonatkozó feltételek együttható mátrixát, relációjeleket és a jobb oldalt!
| Együtthatók | Relációk | Jobb oldal
1. feladó |  | x11 |  | x12 |  | x13 |  | x14 |  |
2. feladó |  | x21 |  | x22 |  | x23 |  | x24 |  |
3. feladó |  | x31 |  | x32 |  | x33 |  | x34 |  |
Ha kisebb egyenlő, vagy nagyobb egyenlő relációt kell írnia, akkor azt így adja meg: <=, illetve >=. | c) Írja fel az igénylőkre vonatkozó feltételrendszer együttható mátrixát, a relációjeleket és a jobb oldalt!
| Együttható mátrix | Reláció | Jobb oldal
1. megrendelő |  | x11 |  | x21 |  | x31 |  |
2. megrendelő |  | x12 |  | x22 |  | x32 |  |
3. megrendelő |  | x13 |  | x23 |  | x33 |  |
4. megrendelő |  | x14 |  | x24 |  | x34 |  |
| Nyisson meg egy Excel-táblát! Helyezze el a költségmátrixot a C5:F7 tartományban. A változók értékei a C11:F13 tartományban legyenek olvashatók. A költségfüggvény (célfüggvény) legyen a D16 cellában. A többi szükséges lépést Önre bízzuk. Ha kész, hívja meg a Solver programot, és oldja meg a feladatot!
| Az optimális megoldást írja a következő Xij mátrixba.
| d) Adja meg az összes költség értékét! Az összes költség:
| 2. Egy vállalkozás 3 telephelyen azonos terméket gyárt. Az egyes telephelyekről a termékeket kamionnal szállítják a megrendelőkhöz. A cég szeretné a szállítási költségeket minimalizálni. A telephelyek kapacitását és a megrendelők igényét az alábbi táblázat tartalmazza:
Telephely | A | B | C | D | Termelés
Szállítási költség (eFt/km)
I. | 45 | 51 | 65 | 88 | 65
II. | 35 | 41 | 70 | 76 | 115
III. | 100 | 59 | 39 | 69 | 85
Igény | 70 | 62 | 70 | 58 | kamion
| A III. telephelyről a B megrendelőhöz nem tudnak szállítani.
| Hívja meg a Solver programot, jelölje be a kért adatokat és a szükséges beállításokat.
| a) Írja fel a feladat lineáris programozási modelljét! Vegyen elő egy lapot, ott írja fel a feltételi egyenleteket és a célfüggvényt. Ezt használja a kérdések megválaszolására.
Ha kisebb-egyenlő, vagy nagyobb-egyenlő relációt kell írnia, akkor azt így adja meg: <=, illetve >=. | b) Írja fel a feladókra vonatkozó feltételek együttható mátrixát, relációjeleket és a jobb oldalt!
| Együtthatók | Relációk | Jobb oldal
1. telephely |  | x11 |  | x12 |  | x13 |  | x14 |  |
2. telephely |  | x21 |  | x22 |  | x23 |  | x24 |  |
3. telephely |  | x31 |  | x32 |  | x33 |  | x34 |  |
Ha kisebb egyenlő, vagy nagyobb egyenlő relációt kell írnia, akkor azt így adja meg: <=, illetve >=. | c) Írja fel az igénylőkre vonatkozó feltételrendszer együttható mátrixát, a relációjeleket és a jobb oldalt!
| Együttható mátrix | Reláció | Jobb oldal
1. megrendelő |  | x11 |  | x21 |  | x31 |  |
2. megrendelő |  | x12 |  | x22 |  | x32 |  |
3. megrendelő |  | x13 |  | x23 |  | x33 |  |
4. megrendelő |  | x14 |  | x24 |  | x34 |  |
| Nyisson meg egy Excel-táblát! Helyezze el a költségmátrixot és a Solver programmal oldja meg a feladatot!
| Az optimális megoldást írja a következő Xij mátrixba.
| d) Adja meg az összes költség értékét! Az összes költség:
| Végezze el az érzékenységvizsgálatot, és nyissa meg az érzékenységvizsgálat munkalapot!
| d) Írja be az árnyékár értékeit a megfelelő helyre!
| Árnyékár
1. telephely |
2. telephely |
3. telephely |
A megrendelő |
B megrendelő |
C megrendelő |
D megrendelő |